package nc.hw;

public class HJ24 {

    public static void main(String[] args) {
        System.out.println(lessNeedOut(new int[]{186,186,150,200,160,130,197,200}));
    }

    private static int lessNeedOut(int[] nums) {
        // 从前往后看每个数最左边最多可以几个人
        int[] leftMax = new int[nums.length];
        leftMax[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && max < leftMax[j] + 1) {
                    max = leftMax[j] + 1;
                }
            }
            leftMax[i] = max;
        }
        int[] rightMax = new int[nums.length];
        rightMax[nums.length - 1] = 0;
        for (int i = nums.length - 2; i >= 0; i --) {
            int max = 0;
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j] < nums[i] && max < rightMax[j] + 1) {
                    max = rightMax[j] + 1;
                }
            }
            rightMax[i] = max;
        }
        int[] all = new int[nums.length];
        int allMax = 0;
        for (int i = 0; i < nums.length; i++) {
            all[i] = leftMax[i] + rightMax[i] + 1;
            if (allMax < all[i]) {
                allMax = all[i];
            }
        }
        return nums.length - allMax;
    }

}
